package java学习.leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * @author 刘世锦
 * 2022-11-21 21:04:37	 当前时间
 */
//给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [3,9,20,null,null,15,7]
//输出：[[15,7],[9,20],[3]]
// 
//
// 示例 2： 
//
// 
//输入：root = [1]
//输出：[[1]]
// 
//
// 示例 3： 
//
// 
//输入：root = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目在范围 [0, 2000] 内 
// -1000 <= Node.val <= 1000 
// 
// Related Topics 树 广度优先搜索 二叉树 
// 👍 632 👎 0

public class 二叉树的层序遍历II{
	public static void main(String[] args) {
		Solution solution = new 二叉树的层序遍历II().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
	/**
	 *
	 *  _ 15 17  _
	 *  3 9 20
	 *  3 9 20 15 7
	 */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
		List<List<Integer>> result = new ArrayList<>();
		ArrayDeque<TreeNode> deque = new ArrayDeque<>();
		if (root!=null){
			deque.offer(root);
			while (!deque.isEmpty()){
				ArrayList<Integer> list = new ArrayList<>();
				int len = deque.size();
				while (len>0){
					TreeNode node = deque.pop();
					list.add(node.val);
					if (node.left!=null){
						deque.offer(node.left);
					}
					if (node.right!=null){
						deque.offer(node.right);
					}
					len--;
				}
				result.add(0,list);
			}

		}
//		List<List<Integer>> resultr = new ArrayList<>();
//		for (int i = result.size()-1; i >=0 ; i--) {
//			resultr.add(result.get(i));
//		}
//		return resultr;
		return result;
    }
}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode() {}
		TreeNode(int val) { this.val = val; }
		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
//leetcode submit region end(Prohibit modification and deletion)

}
